/**
 * @ClassName KP34_
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/11/1 10:56
 */

/**
 * 是否是二叉搜索树
 */
public class KP34_IsBinarySearchTree {
    // 测试链接：https://leetcode.cn/problems/validate-binary-search-tree/

    public static class TreeNode {
        public int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBSTChild(root).isBST;
    }

    public Info isValidBSTChild(TreeNode root) {
        if (root == null) {
            return null;
        }
        Info leftInfo = isValidBSTChild(root.left);
        Info rightInfo = isValidBSTChild(root.right);

        int max = root.val;
        int min = root.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }

        boolean isBST = true;
        boolean leftIsBst = leftInfo == null ? true : leftInfo.isBST && leftInfo.max < root.val;
        boolean rightIsBst = rightInfo == null ? true : rightInfo.isBST && rightInfo.min > root.val;
        if (!(leftIsBst && rightIsBst)) {
            isBST = false;
        }
        return new Info(isBST, max, min);
    }
}
